{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Unique Flavors After Sharing K Candies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shareCandies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分享 K 个糖果后独特口味的数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>您将获得一个 <strong>从0开始的</strong> 整数数组 <code>candies</code> ，其中 <code>`candies[i]`</code>表示第 <code>i</code> 个糖果的味道。你妈妈想让你和你妹妹分享这些糖果，给她 <code>k</code> 个 <strong>连续 </strong>的糖果，但你想保留尽可能多的糖果口味。<br />\n",
    "在与妹妹分享后，返回 <strong>最多</strong> 可保留的 <strong>独特</strong> 口味的糖果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> candies = [1,<u>2,2,3</u>,4,3], k = 3\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释:</strong>\n",
    "将[1,3]（含[2,2,3]）范围内的糖果加入[2,2,3]口味。\n",
    "你可以吃各种口味的糖果[1,4,3]。\n",
    "有3种独特的口味，所以返回3。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> candies = [2,2,2,<u>2,3</u>,3], k = 2\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong>\n",
    "在[3,4]范围内（含[2,3]）的糖果中加入[2,3]口味。\n",
    "你可以吃各种口味的糖果[2,2,2,3]。\n",
    "有两种独特的口味，所以返回2。\n",
    "请注意，你也可以分享口味为[2,2]的糖果，吃口味为[2,2,3,3]的糖果。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> candies = [2,4,5], k = 0\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释:</strong>\n",
    "你不必给任何糖果。\n",
    "你可以吃各种口味的糖果[2,4,5]。\n",
    "有3种独特的口味，所以返回3。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= candies.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= candies[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= candies.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-unique-flavors-after-sharing-k-candies](https://leetcode.cn/problems/number-of-unique-flavors-after-sharing-k-candies/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-unique-flavors-after-sharing-k-candies](https://leetcode.cn/problems/number-of-unique-flavors-after-sharing-k-candies/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,2,3,4,3]\\n3', '[2,2,2,2,3,3]\\n2', '[2,4,5]\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shareCandies(self, candies: List[int], k: int) -> int:\n",
    "        length = len(candies)\n",
    "        candy_dict = collections.defaultdict(int)\n",
    "        for i in range(k, length):\n",
    "            # Do not add the k before\n",
    "            candy_dict[candies[i]] += 1\n",
    "        res = len(candy_dict)\n",
    "        for i in range(length - k):\n",
    "            candy_dict[candies[i]] += 1\n",
    "            candy_dict[candies[i + k]] -= 1\n",
    "            if candy_dict[candies[i + k]] == 0:\n",
    "                del(candy_dict[candies[i + k]])\n",
    "            res = max(res, len(candy_dict))\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shareCandies(self, candies: List[int], k: int) -> int:\n",
    "        numDict = dict()\n",
    "        n = len(candies)\n",
    "        for i in range(k, n):\n",
    "            numDict[candies[i]] = numDict.get(candies[i], 0) + 1\n",
    "        \n",
    "        ans = len(numDict)\n",
    "        for i in range(n - k):\n",
    "            numDict[candies[i]] = numDict.get(candies[i], 0) + 1\n",
    "            numDict[candies[i + k]] -= 1\n",
    "            if numDict[candies[i + k]] == 0:\n",
    "                del numDict[candies[i + k]]\n",
    "            ans = max(ans, len(numDict))\n",
    "            if ans == n - k:\n",
    "                return ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shareCandies(self, candies: List[int], k: int) -> int:\n",
    "        cnt = Counter(candies[k:])\n",
    "        ans = len(cnt)\n",
    "        for i in range(k, len(candies)):\n",
    "            cnt[candies[i - k]] += 1\n",
    "            cnt[candies[i]] -= 1\n",
    "            if cnt[candies[i]] == 0:\n",
    "                cnt.pop(candies[i])\n",
    "            ans = max(ans, len(cnt))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shareCandies(self, candies: List[int], k: int) -> int:        \n",
    "        n = len(candies)\n",
    "        cnt = Counter(candies[k:])\n",
    "        ans = len(cnt)\n",
    "        for i in range(1, n - k + 1):\n",
    "            cnt[candies[i - 1]] += 1\n",
    "            cnt[candies[i + k - 1]] -= 1\n",
    "            if cnt[candies[i + k - 1]] == 0:\n",
    "                del cnt[candies[i + k - 1]]\n",
    "            if len(cnt) > ans:\n",
    "                ans = len(cnt)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shareCandies(self, candies: List[int], k: int) -> int:\n",
    "        d=defaultdict(int)\n",
    "        for i in candies:\n",
    "            d[i]+=1\n",
    "        n=len(d.keys())\n",
    "        \n",
    "        for i in range(k):\n",
    "            if d[candies[i]]==1:\n",
    "                n-=1\n",
    "            d[candies[i]]-=1\n",
    "        ans=n\n",
    "        for i in range(k,len(candies)):\n",
    "            d[candies[i]]-=1\n",
    "            if d[candies[i]]==0:\n",
    "                n-=1\n",
    "            d[candies[i-k]]+=1\n",
    "            if d[candies[i-k]]==1:\n",
    "                n+=1\n",
    "            ans=max(ans,n)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shareCandies(self, candies: List[int], k: int) -> int:\n",
    "        n=len(set(candies))\n",
    "        cnt=Counter(candies)\n",
    "        for i in range(k):\n",
    "            cnt[candies[i]]-=1\n",
    "            if cnt[candies[i]]==0:\n",
    "                del cnt[candies[i]]\n",
    "        ans=len(cnt)\n",
    "        for i in range(k,len(candies)):\n",
    "            cnt[candies[i-k]]+=1\n",
    "            cnt[candies[i]]-=1\n",
    "            if cnt[candies[i]]==0:\n",
    "                del cnt[candies[i]]\n",
    "            ans=max(ans,len(cnt))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# # 定长滑窗\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def shareCandies(self, candies: List[int], k: int) -> int:\n",
    "        counter = Counter(candies)\n",
    "        if k == 0:\n",
    "            return len(counter)\n",
    "\n",
    "        res = 0\n",
    "        for right, cur in enumerate(candies):\n",
    "            counter[cur] -= 1\n",
    "            if counter[cur]==0:\n",
    "                del counter[cur]\n",
    "\n",
    "            if right >= k:\n",
    "                counter[candies[right - k]] += 1\n",
    "\n",
    "            if right >= k - 1:\n",
    "                res = max(res, len(counter))\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shareCandies(self, candies: List[int], k: int) -> int:\n",
    "        n = len(candies)\n",
    "        cnt = Counter(candies)\n",
    "        for i in range(k):\n",
    "            x = candies[i]\n",
    "            cnt[x] -= 1\n",
    "            if cnt[x] == 0:\n",
    "                del cnt[x]\n",
    "        ans = len(cnt)\n",
    "        for i in range(k, n):\n",
    "            x, y = candies[i], candies[i-k]\n",
    "            cnt[y] += 1\n",
    "            cnt[x] -= 1\n",
    "            if cnt[x] == 0:\n",
    "                del cnt[x]\n",
    "            ans = max(ans, len(cnt))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shareCandies(self, candies: List[int], k: int) -> int:\n",
    "        counter = Counter(candies)\n",
    "        if k == 0:\n",
    "            return len(counter)\n",
    "\n",
    "        res = 0\n",
    "        for right, cur in enumerate(candies):\n",
    "            counter[cur] -= 1\n",
    "            if counter[cur]==0:\n",
    "                del counter[cur]\n",
    "            if right >= k:\n",
    "                counter[candies[right - k]] += 1\n",
    "            if right >= k - 1:\n",
    "                res = max(res, len(counter))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# # 定长滑窗\n",
    "from typing import List\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def shareCandies(self, candies: List[int], k: int) -> int:\n",
    "        counter = Counter(candies)\n",
    "        if k == 0:\n",
    "            return len(counter)\n",
    "\n",
    "        res = 0\n",
    "        for right, cur in enumerate(candies):\n",
    "            counter[cur] -= 1\n",
    "            if counter[cur]==0:\n",
    "                del counter[cur]\n",
    "\n",
    "            if right >= k:\n",
    "                counter[candies[right - k]] += 1\n",
    "\n",
    "            if right >= k - 1:\n",
    "                res = max(res, len(counter))\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shareCandies(self, candies: List[int], k: int) -> int:\n",
    "        cnts = Counter(candies)\n",
    "        for i in range(k):\n",
    "            cnts[candies[i]]-=1\n",
    "            if not cnts[candies[i]]:\n",
    "                del cnts[candies[i]]\n",
    "        ans = len(cnts)\n",
    "        for i in range(k,len(candies)):\n",
    "            cnts[candies[i-k]]+=1\n",
    "            cnts[candies[i]]-=1\n",
    "            if not cnts[candies[i]]:\n",
    "                del cnts[candies[i]]\n",
    "            ans = max(ans,len(cnts))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shareCandies(self, candies: List[int], k: int) -> int:\n",
    "\n",
    "        dic={}\n",
    "        w_dic={}\n",
    "\n",
    "        for i in candies[k:]:\n",
    "            if dic.get(i)==None:\n",
    "                dic[i]=1\n",
    "            else:\n",
    "                dic[i]+=1\n",
    "        for i in candies[:k]:\n",
    "            if w_dic.get(i)==None:\n",
    "                w_dic[i]=1\n",
    "            else:\n",
    "                w_dic[i]+=1\n",
    "\n",
    "        left=0\n",
    "        right=k-1\n",
    "        num=0\n",
    "        while right<=(len(candies)-1):\n",
    "            if right<0:\n",
    "                if num==0:\n",
    "                    return len(set(candies))\n",
    "                else:\n",
    "                    break\n",
    "            num=max(num,len(dic.keys()))\n",
    "            w_dic[candies[left]]-=1\n",
    "            if w_dic[candies[left]]==0:\n",
    "                del w_dic[candies[left]]\n",
    "            if dic.get(candies[left])==None:\n",
    "                dic[candies[left]]=1\n",
    "            else:\n",
    "                dic[candies[left]]+=1\n",
    "            left+=1\n",
    "            right+=1\n",
    "            if right>(len(candies)-1):\n",
    "                break\n",
    "            if w_dic.get(candies[right])==None:\n",
    "                w_dic[candies[right]]=1\n",
    "            else:\n",
    "                w_dic[candies[right]]+=1\n",
    "            dic[candies[right]]-=1\n",
    "            if dic[candies[right]]==0:\n",
    "                del dic[candies[right]]\n",
    "            \n",
    "        return num\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shareCandies(self, candies: List[int], k: int) -> int:\n",
    "\n",
    "        dic={}\n",
    "        w_dic={}\n",
    "\n",
    "        for i in candies[k:]:\n",
    "            if dic.get(i)==None:\n",
    "                dic[i]=1\n",
    "            else:\n",
    "                dic[i]+=1\n",
    "        for i in candies[:k]:\n",
    "            if w_dic.get(i)==None:\n",
    "                w_dic[i]=1\n",
    "            else:\n",
    "                w_dic[i]+=1\n",
    "\n",
    "        left=0\n",
    "        right=k-1\n",
    "        num=0\n",
    "        while right<=(len(candies)-1):\n",
    "            if right<0:\n",
    "                if num==0:\n",
    "                    return len(set(candies))\n",
    " \n",
    "            num=max(num,len(dic.keys()))\n",
    "            w_dic[candies[left]]-=1\n",
    "            if w_dic[candies[left]]==0:\n",
    "                del w_dic[candies[left]]\n",
    "            if dic.get(candies[left])==None:\n",
    "                dic[candies[left]]=1\n",
    "            else:\n",
    "                dic[candies[left]]+=1\n",
    "            left+=1\n",
    "            right+=1\n",
    "            if right>(len(candies)-1):\n",
    "                break\n",
    "            if w_dic.get(candies[right])==None:\n",
    "                w_dic[candies[right]]=1\n",
    "            else:\n",
    "                w_dic[candies[right]]+=1\n",
    "            dic[candies[right]]-=1\n",
    "            if dic[candies[right]]==0:\n",
    "                del dic[candies[right]]\n",
    "            \n",
    "        return num\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shareCandies(self, candies: List[int], k: int) -> int:\n",
    "        left = 0\n",
    "\n",
    "        need = {}\n",
    "        for i in candies:\n",
    "            if i not in need.keys():\n",
    "                need[i] = 0\n",
    "            need[i] += 1\n",
    "\n",
    "        window = defaultdict(lambda: 0)\n",
    "        res = 0\n",
    "\n",
    "        ans = len(need.keys())\n",
    "\n",
    "        for right in range(len(candies)):\n",
    "            c = candies[right]\n",
    "            \n",
    "            window[c] += 1\n",
    "            # 如果此时窗口内的c满足\n",
    "            if window[c] == need[c]:\n",
    "                res += 1\n",
    "\n",
    "            if right >= k:\n",
    "                d = candies[left]\n",
    "                left += 1\n",
    "                # 如果出窗口是全部的d\n",
    "                if window[d] == need[d]:\n",
    "                    res -= 1\n",
    "\n",
    "                window[d] -= 1\n",
    "                # print(left, right, window, res)\n",
    "            if right - left == k - 1:\n",
    "                ans = min(res, ans)\n",
    "\n",
    "\n",
    "        return len(need.keys()) - ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
